#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Solution
{
public:
    vector<int> shortestToChar(string s, char c)
    {
        int n = s.length();
        vector<int> ans(n);
        for (int i = 0, idx = -n; i < n; ++i)
        {
            if (s[i] == c)
            {
                idx = i;
            }
            ans[i] = i - idx;
            // cout << ans[i] << " ";
        }
        // cout << endl;
        for (int i = n - 1, idx = 2 * n; i >= 0; --i)
        {
            if (!ans[i])
            {
                idx = i;
            }
            ans[i] = min(ans[i], idx - i);
        }
        return ans;
    }

    vector<int> shortestToChar_2(string s, char c)
    {
        int n = s.length();
        vector<int> ans(n, -1);
        queue<int> indexQueue;
        for (int i = 0; i < n; i++)
        {
            if (c == s[i])
            {
                indexQueue.push(i);
                ans[i] = 0;
            }
        }

        vector<int> dirs = {-1, 1};
        while (!indexQueue.empty())
        {
            int t = indexQueue.front();
            indexQueue.pop();
            for (auto &dir : dirs)
            {
                int ne = t + dir;
                if (ne >= 0 && ne < n && ans[ne] == -1)
                {
                    ans[ne] = ans[t] + 1;
                    // 0-1-2-3 push
                    indexQueue.push(ne);
                }
            }
        }
        return ans;
    }
};
int main()
{
    Solution s;
    string str = "loveleetcode";
    char c = 'e';
    vector<int> ans = s.shortestToChar_2(str, c);
    for (auto &a : ans)
    {
        cout << a << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}
